package arithmetic.LeetCode;

/**
 * @author jiangfeng 2019/7/25 10:35 最长回文子串 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 示例 1：
 *
 * 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2：
 *
 * 输入: "cbbd" 输出: "bb"
 *
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 */
public class LongestPalindromicSubstring {

    public static void main(String[] args) {
        String test1 = "babad";// bab
        String test2 = "cbbd";// bb
        String test3 = "aaabaaaa";// bb
        String test4 = "eabcb";// bb
//        System.out.println(longestPalindrome3(test1));
//        System.out.println(longestPalindrome3(test2));
//        System.out.println(longestPalindrome3(test3));
        System.out.println(longestPalindrome4(test4));
    }

    public static String longestPalindrome4(String s) {
        int longest=1;
        String result = s.substring(0,1);
        int len = s.length();
        if(len==1){
            return result;
        }
        int step = len*2-1;
        // 中心扩展
        for(int i=0;i<step;i++){
            //偶数用字母，奇数在间隙
            int l = i/2 ;
            int r = i/2 + (i%2==0?0:1);
            while(l>=0&&r<len){
                if(s.charAt(l)!=s.charAt(r)) {
                    break;
                }
                if(longest<(r-l+1)){
                    longest = r-l+1;
                    result = s.substring(l,r+1);
                }
                l--;
                r++;
            }
        }
        return result;
    }

    //HashMap

    /**
     * 思路1 暴力破解,循环判断  时间复杂度是 n的三次方 两层循环加上判断又是一层循环... 超出时间限制. 空间复杂度是1
     */
    public static String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        String result = "";
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (isPalind(chars, i, j) && j - i + 1 > result.length()) {
                    result = s.substring(i, j + 1);
                }
            }
        }
        return result;
    }

    public static boolean isPalind(char[] chars, int i, int j) {
        while (i <= j) {
            if (chars[i++] != chars[j--]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 思路2 动态规划. 大问题转成小问题. 如果i到j是回文, 则必有a[i]==a[j] && a[i+1]==a[j-1]  (i<j);  时间:n的2次方,空间复杂度n2
     * @return
     */
    public static String longestPalindrome2(String s){
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[s.length()][s.length()];
        String result = "";
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (i == j) {
                    dp[i][j] = true;
                } else if (j - i == 1 && chars[i] == chars[j]) {
                    dp[i][j] = true;
                } else if (j - i > 1 && chars[i] == chars[j] && dp[i+1][j-1]) {
                    dp[i][j] = true;
                }
                if (dp[i][j] && j - i + 1 > result.length()) {
                    result = s.substring(i, j + 1);
                }
            }
        }
        return result;
    }

    /**
     * 思路3 中心扩展法
     */
    public static String longestPalindrome3(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expendCenterSize(s, i, i);
            int len2 = expendCenterSize(s, i, i + 1);
            int len=len1>len2?len1:len2;
            if (len > end-start+1){
                start= i-(len-1)/2;
                end = i+len/2;
            }
        }

        return s.substring(start,end+1);
    }

    public static int expendCenterSize(String s, int l, int r) {
        while (l <= r && l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        //l和r超过边界了
        l++;r--;
        return r - l+1;
    }

}
